package bag;

/**
 * 两个代码优化
 * 1. 二维缩减为1维数组
 * 2. if简化到了 for循环中  保证 i> coins[j]  ->  for(int i = coins[j]; i< amount + 1; i++)
 *      这个在 零钱兑换_322 中的一维数组处理中没有这么简化
 */

class 零钱兑换II_518_重做版 {
    public int change(int amount, int[] coins) {


        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for(int i = 0; i< coins.length; i++) {
            for(int j = 1; j< amount + 1; j++) {
                if(j >= coins[i])
                    dp[j] += dp[j - coins[i]]; // 二维省略成一维   dp[i][j] 表示 前i个硬币中 组成j有多少种组合   dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i]] // 顺理成章去掉第一维
            }
        }
        return dp[amount];
    }
}

public class 零钱兑换II_518 {
    public int change(int amount, int[] coins) {


        int [] dp = new int[amount + 1];
        dp[0] = 1;
        for(int j =0; j< coins.length; ++j) {
            // i > coins[j] 才会更新求和
            // i< coins[j] 时 dp[i] 不能加上当前硬币，因而dp[i] 不变
            // dp[i] = 其他dp[i-coins[j]] 之和
            for(int i = coins[j]; i< amount + 1; i++) {
                // dp[i] 的组合数等于 组合之和
                // 因为后面的需要根据前面的来修改叠加  因此正向循环
                dp[i] = dp[i] + dp[i - coins[j] ];
            }
        }
        return dp[amount];
    }


    public static void main(String[] args) {
        零钱兑换II_518 a = new 零钱兑换II_518();
        int change = a.change(5, new int[]{1, 2, 5});
        System.out.println(change);
    }
}